home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / VECTOR.C < prev    next >
C/C++ Source or Header  |  1992-09-29  |  33KB  |  859 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Updated: JAM 08/12/92 -- modernize template syntax, remove macro hacks
  13. // Updated: JAM 08/12/92 -- split up comma expr in some funcs because of
  14. //                          a a BC++ bug when Type was a float or double
  15.  
  16. #ifndef VECTORC
  17. #define VECTORC
  18.  
  19. #include <cool/Vector.h>
  20.  
  21. // compare_s -- static data member of CoolVector, pointer to Type operator== 
  22. template<class Type> 
  23. Boolean (*CoolVector<Type>::compare_s)(const Type&, const Type&) = &CoolVector_is_data_equal;
  24.  
  25. // CoolVector<Type> () -- Empty constructor for the CoolVector class.
  26. // Input:             None
  27. // Output:            None
  28.  
  29. template<class Type> 
  30. CoolVector<Type>::CoolVector () {
  31.   this->data = NULL;                // NULL data pointer
  32. }
  33.  
  34.  
  35. // CoolVector<Type> (size_t) -- constructor that specifies number of elements.
  36. // Input:                 Number of elements 
  37. // Output:                None
  38.  
  39. template<class Type> 
  40. CoolVector<Type>::CoolVector (size_t n)
  41.  : CoolBaseVector(n)
  42. {
  43.   this->data  = new Type[n];        // Allocate memory
  44. }
  45.  
  46.  
  47. // CoolVector<Type> (void*, size_t) -- constructor that specifies user-defined static
  48. //                               size storage and number of elements
  49. // Input:                        Pointer to storage, number of elements 
  50. // Output:                       None
  51.  
  52. template<class Type> 
  53. CoolVector<Type>::CoolVector (void* s, size_t n)
  54.  : CoolBaseVector(n)
  55. {
  56.   this->data  = (Type*) s;            // Pointer to storage block
  57.   this->alloc_size = INVALID_ALLOCSZ();            // Indicate static-size object
  58. }
  59.  
  60.  
  61. // CoolVector<Type> (size_t, Type&) -- constructor that specifies number of elements
  62. //                               and also an initialization value to set all
  63. //                               elements.
  64. // Input:   Number of elements and Type reference to initialization value
  65. // Output:  None
  66.  
  67. template<class Type> 
  68. CoolVector<Type>::CoolVector (size_t n, const Type& value)
  69.  : CoolBaseVector(n)
  70. {
  71.   this->data = new Type[n];            // Allocate memory
  72.   for (size_t i = 0; i < n; i++)            // For each element in Vector
  73.     this->data[i] = value;            // Set initial value
  74.   this->number_elements = n;            // Set element count
  75. }
  76.  
  77.  
  78. // CoolVector<Type> (size_t,size_t, ...) -- constructor that specifies number of elements
  79. //                                 and also a variable number of references to
  80. //                                 initialization values for successive elements
  81. //                                 in the vector. 
  82. // Input:   Number of elements, number of initial values, and initial values
  83. // Output:  None
  84. // Note: Arguments in ... can only be pointers, primitive types like int,
  85. //       and NOT OBJECTS, passed by reference or value, like vectors, matrices;
  86. //       because constructors must be known and called at compile time!!!
  87. //       Cannot have char in ..., because char is 1 instead of 4 bytes, and 
  88. //       va_arg expects sizeof(Type) a multiple of 4 bytes.
  89.  
  90. template<class Type> 
  91. CoolVector<Type>::CoolVector (size_t n, size_t nv, Type v0, ...)
  92.  : CoolBaseVector(n)
  93. {
  94. #if ERROR_CHECKING
  95.   if (((sizeof(Type) % 4) != 0) ||        // Cause alignment problems
  96.       (sizeof(Type) > 8))            // User defined classes?
  97.     this->va_arg_error(#Type, sizeof(Type));    // So, cannot use this constructor
  98. #endif
  99.   typedef Type xType; // need Type expanded all the way before call to macro va_arg
  100.  
  101.   this->data = new Type[n];            // Allocate memory
  102.   this->number_elements = nv;            // Update element count
  103.   this->data[0] = v0;
  104.   va_list argp;                    // Declare argument list
  105.   va_start (argp, v0);                // Initialize macro
  106.   for (size_t i = 1; i < nv; i++)            // For remaining values given
  107.     //this->data[i] = va_arg(argp,Type);        // Extract and assign 
  108.     this->data[i] = va_arg(argp, xType);        // for v2.1 with fakeup cpp
  109.   va_end (argp);
  110. }
  111.  
  112.  
  113. // CoolVector<Type> (CoolVector<Type>&) -- Copy constructor
  114. // Input:   CoolVector reference
  115. // Output:  None
  116.  
  117. template<class Type> 
  118. CoolVector<Type>::CoolVector (const CoolVector<Type>& v)
  119.  : CoolBaseVector(v)
  120. {
  121.   this->data = new Type[v.size];    // Allocate enough storage
  122.   for (size_t i = 0; i < v.number_elements; i++)    // For each element in CoolVector
  123.      this->data[i] = v.data[i];            // Copy value
  124. }
  125.  
  126.  
  127. // ~CoolVector<Type> () -- Destructor for CoolVector class that frees up storage.
  128. // Input:              None
  129. // Output:             None
  130.  
  131. template<class Type> 
  132. CoolVector<Type>::~CoolVector () {
  133.   if (this->size != 0 &&
  134.       this->alloc_size != INVALID_ALLOCSZ())        // If not user-provide storage
  135.     delete [] this->data;            // Free up the memory
  136. }
  137.  
  138. // void fill () -- Fill elements `start' through `end' inclusive with valuen
  139. // Input:          Type reference, start inclusive, and end index exclusive
  140. // Output:         None
  141.  
  142.  
  143. template<class Type> 
  144. void CoolVector<Type>::fill (const Type& value, size_t start, size_t end) {
  145. #if ERROR_CHECKING  
  146.   if (start >= this->number_elements)        // If start out of range
  147.     this->fill_start_error (#Type, start);    // Raise exception
  148.   if (end < start || end > this->number_elements) // If end out of range
  149.     this->fill_end_error (#Type, end);        // Raise exception
  150. #endif
  151.   for (size_t i = start; i < end; i++)        // For each element in range
  152.     this->data[i] = value;            // Assign new value
  153.   this->curpos = INVALID_ALLOCSZ();            // Invalidate current position
  154. }
  155.  
  156.  
  157. // void copy () -- Copy a specified range of elements from one vector to this
  158. // Input:          CoolVector reference, start inclusive, and end index exclusive
  159. // Output:         None
  160.  
  161. template<class Type> 
  162. void CoolVector<Type>::copy (const CoolVector<Type>& v, size_t start, size_t end){
  163. #if ERROR_CHECKING  
  164.   if (start >= v.number_elements)        // If start out of range
  165.     this->copy_start_error (#Type, start);    // Raise exception
  166.   if (end < start || end > v.number_elements)    // If end out of range
  167.     this->copy_end_error (#Type, end);        // Raise exception
  168. #endif
  169.   if (this->size < end) {            // If not enough memory
  170. #if ERROR_CHECKING
  171.     if (alloc_size == INVALID_ALLOCSZ())            // If static size vector
  172.       this->copy_error (#Type);            // Raise exception
  173. #endif
  174.     this->grow(end);
  175.   }
  176.   for (size_t i = start; i < end; i++)        // For each element in range
  177.     this->data[i] = v.data[i];            // Assign new value
  178.   if (i > this->number_elements)        // If we added new elements
  179.     this->number_elements = i;            // Update element count
  180.   this->curpos = i;                // Update current position
  181. }
  182.  
  183.  
  184. // search -- Find a subsequence of elements in a CoolVector
  185. // Input:    CoolVector reference to subsequence searching for,
  186. //           start inclusive, and end index exclusive
  187. // Output:   TRUE/FALSE; current position updated if found
  188.  
  189. template<class Type> 
  190. Boolean CoolVector<Type>::search (const CoolVector<Type>& v, size_t start, size_t end) {
  191.   register size_t i, j;
  192.   end -= v.number_elements;
  193.   for (i = start; i < end; i++) {        // Find start of subsequence
  194.     for (j = 0; j < v.number_elements; j++)
  195.       if (!(*this->compare_s)(this->data[i+j],v.data[j])) // If not equal
  196.     goto again2;                      // try again
  197.  
  198.     this->curpos = i;                // Point to start of sequence
  199.     return TRUE;                // Return starting index
  200.   again2:;
  201.   }
  202.   return FALSE;
  203. }
  204.  
  205.  
  206. // Boolean operator== () -- Compare the elements of this CoolVector with a second
  207. // Input:                   Reference to vector object
  208. // Output:                  TRUE/FALSE
  209.  
  210.   template<class Type> 
  211. Boolean CoolVector<Type>::operator== (const CoolVector<Type>& v) const {
  212.   register size_t i;
  213.   if (this->number_elements != v.number_elements) // If not same number
  214.     return FALSE;                  // Then not equal
  215.   for (i = 0; i < this->number_elements; i++)      // For each element in vector
  216.     if (!(*this->compare_s)(this->data[i],v.data[i]))
  217.       return FALSE;
  218.   return TRUE;
  219. }
  220.  
  221.  
  222. // Boolean is_data_equal () -- Default data comparison function if user has
  223. //                             not provided another method
  224. // Input:                      Two Type references
  225. // Output:                     TRUE/FALSE
  226.  
  227. template<class Type>
  228. Boolean CoolVector_is_data_equal (const Type& t1, const Type& t2) {
  229.     return (t1 == t2);
  230. }
  231.  
  232. // void set_compare () -- Specify the comparison function to be used in 
  233. //                        logical comparisons of vector objects
  234. // Input:                 Pointer to a compare function
  235. // Output:                None
  236.  
  237. template<class Type> 
  238. void CoolVector<Type>::set_compare (Boolean (*cf)(const Type&, const Type&)) {
  239.   if (cf)
  240.     this->compare_s = cf;            // Set to user function 
  241.   else
  242.     this->compare_s = &CoolVector_is_data_equal;    // or to default
  243. }
  244.  
  245.  
  246. // CoolVector<Type&> operator= () -- Overload the assignment operator
  247. // Input:                        Reference to CoolVector object
  248. // Output:                       Reference to copied CoolVector object
  249.  
  250. template<class Type> 
  251. CoolVector<Type>& CoolVector<Type>::operator= (const CoolVector<Type>& v) {
  252.   if (this->size < v.size) {            // If not enough memory
  253. #if ERROR_CHECKING
  254.     if (alloc_size == INVALID_ALLOCSZ())            // If static size vector
  255.       this->assign_error (#Type);        // Raise exception
  256. #endif
  257.     if (this->size != 0)
  258.       delete [] this->data;                    // Free it up
  259.     this->data = new Type[v.size];        // and allocate bigger memory
  260.   this->size = v.size;                // Set new vector size
  261.   }
  262.   this->CoolBaseVector::operator= (v);             // Base class assignment
  263.   for (size_t i = 0; i < v.number_elements; i++)    // For each element
  264.     this->data[i] = v.data[i];            // Copy value
  265.   return *this;                    // Return CoolVector reference
  266. }
  267.  
  268.  
  269. // CoolVector<Type>& operator= () -- Overload the assignment operator to assign a
  270. //                               single value to all the elements of a vector
  271. // Input:                        Type reference to fill value
  272. // Output:                       Reference to updated CoolVector object
  273.  
  274. template<class Type> 
  275. CoolVector<Type>& CoolVector<Type>::operator= (const Type& value) {
  276.   for (size_t i = 0; i < this->number_elements; i++) // For each element in CoolVector
  277.     this->data[i] = value;               // Set initial value
  278.   this->curpos = INVALID_POS();               // Point to first element
  279.   return *this;                       // Return CoolVector reference
  280. }
  281.  
  282. // Boolean find () -- Find first/next occurrence of element in a CoolVector.
  283. //                    from start or end of vector respectively if dir = +1, -1.
  284. // Input:             Type reference to search value, starting index
  285. // Output:            TRUE/FALSE
  286.  
  287. template<class Type> 
  288. Boolean CoolVector<Type>::find (const Type& value, size_t start, int dir) {
  289.   register size_t i = start;
  290.   register size_t n = this->number_elements - start; // max number of elmts to search
  291.   if (dir == -1) n = start + 1;
  292.   for (; n > 0; n--, i += dir)
  293.     if ((*(this->compare_s))(this->data[i], value) == TRUE) {
  294.       this->curpos = i;
  295.       return TRUE;
  296.     }
  297.   return FALSE;
  298. }
  299.  
  300. // void grow () -- Adjust the memory size of a CoolVector to accomodate some size
  301. // Input:            Interger number of elements to hold
  302. // Output:           None
  303.  
  304. template<class Type> 
  305. void CoolVector<Type>::grow (size_t min_size) {
  306.   size_t new_size = (size_t)(this->size * (1.0 + growth_ratio)); // New size?
  307.   if (new_size < min_size) new_size = min_size + alloc_size;
  308.   resize(new_size);
  309. }
  310.  
  311. // void resize () -- Adjust the memory size of a CoolVector to accomodate some size
  312. // Input:            Interger number of elements to hold
  313. // Output:           None
  314.  
  315. template<class Type> 
  316. void CoolVector<Type>::resize (size_t new_size) {
  317.   if (new_size <= this->size) {            // Don't bother shrinking
  318. #if ERROR_CHECKING  
  319.     if (new_size < 0)                // If index out of range
  320.       this->resize_error (#Type,new_size);    // Raise exception
  321. #endif
  322.     return;
  323.   }
  324. #if ERROR_CHECKING  
  325.   if (alloc_size == INVALID_ALLOCSZ())            // If static size vector
  326.     this->static_error (#Type);            // Raise exception
  327. #endif
  328.   Type* temp = new Type[new_size];        // Allocate storage
  329.   for (size_t i = 0; i < this->number_elements; i++)// For each element in Vector
  330.     temp[i] = this->data[i];            // Copy into new storage
  331.   if (this->size != 0)
  332.     delete [] this->data;                    // Free up old memory
  333.   this->data = temp;                // Assign new memory block
  334.   this->size = new_size;            // Save new size value
  335. }
  336.  
  337.  
  338. // push -- Add element to end of the CoolVector
  339. // Input:  Type reference
  340. // Output: TRUE if successful, FALSE if could not grow vector
  341.  
  342. template<class Type> 
  343. Boolean CoolVector<Type>::push (const Type& value) {
  344.   if (this->number_elements == this->size) {    // If not enough memory
  345.     if (this->alloc_size == INVALID_ALLOCSZ())        // If not allowed to grow
  346.       return FALSE;                // Return failure flag
  347.     this->grow(this->size+1);            // Else grow the CoolVector
  348.   }
  349.   this->curpos = this->number_elements;        // Set current position
  350.   this->data[this->number_elements++] = value;    // Assign new value
  351.   return TRUE;                    // Return success status
  352. }
  353.  
  354.  
  355. // push_new -- Add an element if it is not already there
  356. // Input:      Reference to Type
  357. // Output:     TRUE/FALSE
  358.  
  359. template<class Type> 
  360. Boolean CoolVector<Type>::push_new (const Type& value) {
  361.   if (this->number_elements == this->size && this->alloc_size == INVALID_ALLOCSZ())
  362.     return FALSE;                // Return failure flag
  363.   if (this->find(value, this->number_elements-1, -1)) 
  364.     return FALSE;        // If already in CoolVector
  365.   if (this->number_elements >= this->size)    // If not enough memory
  366.     this->grow(this->size+1);            // Else grow the Vector
  367.   this->curpos = this->number_elements;        // Set current position
  368.   this->data[this->number_elements++] = value;    // Assign new value
  369.   return TRUE;                    // Return success status
  370. }
  371.  
  372.  
  373. // pop --   Return last element in the CoolVector
  374. // Input:   None
  375. // Output:  Type reference to last element in CoolVector
  376.  
  377. template<class Type> 
  378. Type& CoolVector<Type>::pop () {
  379.   if (this->number_elements > 0) {        // If there are elements
  380.     this->curpos = INVALID_POS();            // Invalidate current position
  381.     return (this->data[--this->number_elements]); // Return the last one
  382.   }
  383. }
  384.  
  385.  
  386. // reverse -- Destructively reverse the order of elements in a CoolVector
  387. // Input:     None
  388. // Output:    None
  389.  
  390. template<class Type> 
  391. void CoolVector<Type>::reverse () {
  392.   Type temp;
  393.   for (size_t i = 0, j = this->number_elements-1;    // Counting from front and rear
  394.        i < this->number_elements / 2; i++, j--) { // until we reach the middle
  395.     temp = this->data[i];            // Save front data item
  396.     this->data[i] = this->data[j];        // Switch with rear data item
  397.     this->data[j] = temp;            // Copy new rear data item
  398.   }
  399.   this->curpos = INVALID_POS();            // Invalidate current position
  400. }
  401.  
  402.  
  403. // remove -- Destructively remove item at current position.
  404. //           Shift remaining elmts to preserve order in vector.
  405. // Input:   None
  406. // Output:  Type reference to item removed
  407.  
  408. template<class Type> 
  409. Type CoolVector<Type>::remove () {
  410.   IterState i = this->curpos;
  411.   if (i == INVALID_POS()) this->remove_error("Type");
  412.   Type value = this->data[i];
  413.   Type* elmts = &this->data[i];            // Shift elements by 1 place
  414.   while (++i < this->number_elements) {        // Copy over current
  415.     *elmts = *(elmts + 1);        // Use assignment of class Type
  416.     elmts++;        // Use assignment of class Type
  417.   }
  418.   this->number_elements--;            // Update element count
  419.   if (this->curpos == this->number_elements)    // If past end of vector
  420.     this->curpos = INVALID_POS();            // Invalidate current position
  421.   return value;                    // Return Vector reference
  422. }
  423.  
  424.  
  425. // remove -- Destructively remove the first occurrence of an element
  426. // Input:   Type reference
  427. // Output:  TRUE if element found and removed, FALSE otherwise
  428.  
  429. template<class Type> 
  430. Boolean CoolVector<Type>::remove (const Type& value, int dir) {
  431.   size_t start = 0;
  432.   if (dir == -1) start = this->number_elements - 1;
  433.   if (this->find(value, start, dir)) {        // When found
  434.     size_t i = this->curpos;
  435.     Type* elmts = &this->data[i];        // Shifts remaining elements
  436.     while (++i < this->number_elements)    {    // by 1 place
  437.       *elmts = *(elmts + 1);        // Use assignment of class Type
  438.       elmts++;        // Use assignment of class Type
  439.     }
  440.     this->number_elements--;            // Update element count
  441.     return TRUE;
  442.   } else 
  443.     return FALSE;
  444. }
  445.  
  446.  
  447. // remove_duplicates -- Destructively remove duplicate elements from CoolVector
  448. // Input:               None
  449. // Output:              TRUE if any removed, FALSE otherwise
  450.  
  451. template<class Type> 
  452. Boolean CoolVector<Type>::remove_duplicates () {
  453.   this->curpos = INVALID_POS();            // Invalidate current position
  454.   if (this->size == 0) return FALSE;
  455.   Boolean success = FALSE;            // Return value
  456.   Type* old = this->data;            // Old data
  457.   this->data = new Type[this->size];        // New data
  458.   size_t n = this->number_elements;        // length of old data
  459.   this->number_elements = 0;
  460.   for (size_t i = 0; i < n; i++) {        // For each element
  461.     if (!this->find(old[i], this->number_elements-1, -1)) { // if not copied yet
  462.       this->data[this->number_elements++] = old[i]; // copy value
  463.       success = TRUE;                // Set flag
  464.     }
  465.   }
  466.   delete [] old;                      // destroy old data
  467.   return success;
  468. }
  469.  
  470.  
  471. // replace -- Destructively replace the first occurrence of an element
  472. // Input:     Two Type references
  473. // Output:    TRUE if element found and replaced, FALSE otherwise
  474.  
  475. template<class Type> 
  476. Boolean CoolVector<Type>::replace (const Type& t1, const Type& t2, int dir) {
  477.   size_t start = 0;
  478.   if (dir == -1) start = this->number_elements -1;
  479.   if (this->find(t1, start, dir)) {
  480.     this->data[this->curpos] = t2;        
  481.     if (dir == +1) this->curpos++;        // Point to item after replace
  482.     else this->curpos--;            // in direction of dir
  483.     if (this->curpos > this->number_elements) this->curpos = INVALID_POS();
  484.     return TRUE;
  485.   } else return FALSE;
  486. }
  487.  
  488.  
  489. // replace_all -- Destructively replace all occurrences of an element
  490. // Input:         Two Type references
  491. // Output:        TRUE if any element replaced, FALSE otherwise
  492.  
  493. template<class Type> 
  494. Boolean CoolVector<Type>::replace_all (const Type& t1, const Type& t2) {
  495.   Boolean success = FALSE;            // Return value
  496.   this->curpos = 0;
  497.   for (;;) {
  498.     if (!this->find(t1, this->curpos, +1)) return success;
  499.     this->data[this->curpos++] = t2;        // Point to item after replace
  500.     if (this->curpos > this->number_elements) this->curpos = INVALID_POS();
  501.   }
  502. }
  503.  
  504.  
  505. // prepend -- Destructively insert the elements of some CoolVector at the beginning
  506. // Input:     CoolVector reference
  507. // Output:    TRUE if successful, FALSE if could not grow CoolVector
  508.  
  509. template<class Type> 
  510. Boolean CoolVector<Type>::prepend (const CoolVector<Type>& v) {
  511.   Type* temp;                    // Declare temporary
  512.   size_t old_size = this->size;            // Keep old size
  513.   size_t new_size = this->number_elements + v.number_elements; // Minimum size
  514.   if (this->size < new_size) {            // Enough memory?
  515.     if (this->alloc_size == INVALID_ALLOCSZ())        // If not allowed to grow
  516.       return FALSE;                // Return failure flag
  517.     this->size = (size_t)(this->size * (1.0 + growth_ratio)); // New size
  518.     if (this->size < new_size)            // If not enough
  519.       this->size = new_size + this->alloc_size;    // use alloc_size
  520.   }
  521.   temp = new Type[this->size];            // Allocate required storage
  522.   for (size_t i = 0; i < v.number_elements; i++)    // For all elements
  523.     temp[i] = v.data[i];            // Copy to beginning of CoolVector
  524.   this->curpos = i;                // Set current position
  525.   for (i = 0; i < this->number_elements; i++)    // For each element
  526.     temp[i+v.number_elements] = this->data[i];  // Copy into new storage
  527.   if (old_size != 0)
  528.     delete [] this->data;                // Free up old memory
  529.   this->data = temp;                // Assign new memory block
  530.   this->number_elements += v.number_elements;    // Update element count
  531.   return TRUE;                    // Return success flag
  532. }
  533.  
  534.  
  535. // append -- Destructively append the elements of some CoolVector at the beginning
  536. // Input:    CoolVector reference
  537. // Output:   TRUE if successful, FALSE if could not grow CoolVector
  538.  
  539. template<class Type> 
  540. Boolean CoolVector<Type>::append (const CoolVector<Type>& v) {
  541.   size_t new_size = this->number_elements + v.number_elements; // Minimum size
  542.   if (this->size < new_size) {            // Enough memory?
  543.     if (this->alloc_size == INVALID_ALLOCSZ())        // If not allowed to grow
  544.       return FALSE;                // Return failure flag
  545.     this->grow(new_size);
  546.   }
  547.   this->curpos = this->number_elements - 1;    // Set current position
  548.   for (size_t i = 0; i < v.number_elements; i++)    // For each element
  549.     this->data[i+this->number_elements] = v.data[i]; // Copy to end of CoolVector
  550.   this->number_elements += v.number_elements;    // Update element count
  551.   return TRUE;                    // Return CoolVector reference
  552. }
  553.  
  554.  
  555. // insert_before -- Destructively insert an element before current position
  556. // Input:           Type reference
  557. // Output:          TRUE if successful, FALSE if could not grow CoolVector
  558.  
  559. template<class Type> 
  560. Boolean CoolVector<Type>::insert_before (const Type&  value) {
  561.   if (this->curpos == INVALID_POS())            // If no current position
  562.     return FALSE;                // Return failure flag
  563.   return this->insert_before(value, this->curpos);
  564. }
  565.  
  566.  
  567. // insert_after -- Destructively insert an element after current position
  568. // Input:          Type reference
  569. // Output:         TRUE if successful, FALSE if could not grow CoolVector
  570.  
  571. template<class Type> 
  572. Boolean CoolVector<Type>::insert_after (const Type&  value) {
  573.   if (this->curpos == INVALID_POS())            // If no current position
  574.     return FALSE;                // Return failure flag
  575.   return this->insert_after(value, this->curpos);
  576. }
  577.  
  578.  
  579. // insert_before -- Destructively insert an element before specified index
  580. // Input:           Type reference and an index position
  581. // Output:          TRUE if successful, FALSE if could not grow CoolVector
  582.  
  583. template<class Type> 
  584. Boolean CoolVector<Type>::insert_before (const Type&  value, size_t index) {
  585.   size_t n = this->number_elements+1;
  586.   if (n >= this->size) {            // If not enough memory
  587.     if (this->alloc_size == INVALID_ALLOCSZ())        // If not allowed to grow
  588.       return FALSE;                // Return failure flag
  589.     this->grow(n);
  590.   }
  591.   this->curpos = index;                // Current position at insertion
  592.   Type* elmts = &this->data[n-1];        // Use operator= of Type
  593.   while (--n > index) {                // shift elements by 1 place
  594.     *elmts = *(elmts - 1);                // Copy over current
  595.     elmts--;
  596.   }    
  597.   this->data[this->curpos] = value;        // Assign new value
  598.   this->number_elements++;
  599.   return TRUE;                    // Return CoolVector reference
  600. }
  601.  
  602.  
  603. // insert_after -- Destructively insert an element after specified index
  604. // Input:          Type reference and an index position
  605. // Output:         TRUE if successful, FALSE if could not grow CoolVector
  606.  
  607. template<class Type> 
  608. Boolean CoolVector<Type>::insert_after (const Type&  value, size_t index) {
  609.   size_t n = this->number_elements+1;
  610.   if (n >= this->size) {            // If not enough memory
  611.     if (this->alloc_size == INVALID_ALLOCSZ())        // If not allowed to grow
  612.       return FALSE;                // Return failure flag
  613.     this->grow(n);
  614.   }
  615.   this->curpos = ++index;            // Current position at insertion
  616.   Type* elmts = &this->data[n-1];        // Use operator= of Type
  617.   while (--n > index) {                // shift elements by 1 place
  618.     *elmts = *(elmts - 1);                // Copy over current
  619.     elmts--;
  620.   }    
  621.   this->data[this->curpos] = value;        // Assign new value
  622.   this->number_elements++;
  623.   return TRUE;                    // Return CoolVector reference
  624. }
  625.  
  626.  
  627.  
  628. // merge -- Destructively merge two CoolVectors of the same size using a user
  629. //          supplied predicate function. The predicate function returns
  630. //          TRUE if and only if the first element preceeds the second.
  631. // Input:   CoolVector reference and pointer to Predicate function
  632. // Output:  None
  633.  
  634. template<class Type> 
  635. void CoolVector<Type>::merge(const CoolVector<Type>& v, int (*pred)(const Type&, const Type&)) {
  636.   size_t old_size = this->size;            // Keep old size
  637.   size_t total = this->number_elements+v.number_elements; // Min space required
  638.   if (this->size < total) {
  639.     this->size = (size_t)(this->size*(1.0+growth_ratio)); // New size by ratio
  640.     if (this->size < total)                  // check growth
  641.       this->size = total + this->alloc_size;          // New size by growth
  642.   }
  643.   Type* temp = new Type[this->size];        // Allocated storage
  644.   for (size_t i=0,j=0,k=0; i < total; i++) {    // For all elements
  645.     if (j >= this->number_elements) {        // If past end of CoolVector
  646.       for (; k < v.number_elements; k++, i++)    // Copy rest of other vector
  647.     temp[i] = v.data[k];            // Copy element value
  648.       break;                    // Break out of loop when done
  649.     }
  650.     else if (k >= v.number_elements) {        // If past end of other vector
  651.       for (; j < this->number_elements;j++,i++) // Copy rest of other vector
  652.     temp[i] = this->data[j];        // Copy element value
  653.       break;                    // Break out of loop when done
  654.     }
  655.     else {
  656.       if ((*pred)(this->data[j], v.data[k]) < 0) // If it goes here
  657.     temp[i] = this->data[j++];        // Copy first element
  658.       else
  659.     temp[i] = v.data[k++];            // Copy second element
  660.     }
  661.   }
  662.   if (old_size != 0)
  663.     delete [] this->data;                // Free up old memory
  664.   this->data = temp;                // Assign new memory block
  665.   this->number_elements = total;        // Update element count
  666.   this->curpos = INVALID_POS();            // Invalidate current position
  667. }
  668.  
  669.  
  670. // sort -- Destructively sort the elements of a vector using the supplied
  671. //         predicate function. The predicate function returns TRUE if and only
  672. //         if the first element preceeds the second. This routine uses the 
  673. //         Heap Sort algorithm as given in "Numerical Recipes in C" p247.
  674. // Input:   Pointer to predicate function
  675. // Output:  None
  676.  
  677. #ifdef __cplusplus
  678.  
  679. #include <stdlib.h>        // include the standard c library
  680.  
  681. template<class Type> 
  682. void CoolVector<Type>::sort (int (*p)(const Type&, const Type&)) {
  683.   if (this->number_elements > 1)        // If more than one element
  684.     qsort((void*) this->data,
  685.       (unsigned int) this->number_elements, sizeof(Type),
  686.       (int(*)(const void*, const void*)) p);
  687. }
  688.  
  689. #else                        // Not all machines have qsort
  690.  
  691. template<class Type> 
  692. void CoolVector<Type>::sort (int (*p)(const Type&, const Type&)) {
  693.   if (this->number_elements > 1) {        // If more than one element
  694.     size_t n = this->number_elements;
  695.     size_t l, j, ir, i;
  696.     Type temp;
  697.     Type* v_prime = this->data - 1;        // Adjust for 1-based index
  698.     l = (n >> 1) + 1;
  699.     ir = n;
  700.     while (TRUE) {
  701.       if (l > 1)
  702.     temp = v_prime[--l];
  703.       else {
  704.     temp = v_prime[ir];
  705.     v_prime[ir] = v_prime[1];
  706.     if (--ir == 1) {
  707.       v_prime[1] = temp;
  708.       break;
  709.     }
  710.       }
  711.       i = l;
  712.       j = i << 1;
  713.       while (j <= ir) {
  714.     if (j < ir && (*p)(v_prime[j], v_prime[j+1]) < 0)
  715.       ++j;
  716.     if ((*p)(temp, v_prime[j]) < 0) {
  717.       v_prime[i] = v_prime[j];
  718.       j += (i = j);
  719.     }
  720.     else
  721.       j = ir + 1;
  722.       }
  723.       v_prime[i] = temp;
  724.     }
  725.     this->curpos = INVALID_POS();            // Invalidate current position
  726.   }
  727. }
  728. #endif
  729.   
  730. // ostream& operator<< () -- Overload the output operator for CoolVector reference
  731. // Input:                    Ostream reference and CoolVector reference
  732. // Output:                   Ostream reference
  733.  
  734. template<class Type>
  735. ostream& operator<< (ostream& os, const CoolVector<Type>& v) {
  736.   if (v.length() == 0)                // If no elements in vector
  737.     os << " Empty ";                // Indicate empty status
  738.   else {
  739.     os << "[ ";
  740.     for (size_t i = 0; i < v.length(); i++)    // For each element
  741.       os << v.data[i] << " ";            // Output value to stream
  742.     os << "]";
  743.   }
  744.   return os;                    // Return ostream reference
  745. }
  746.  
  747.  
  748.  
  749. // shuffle_remove -- Destructively remove item at current position
  750. //           Shuffle last element up to fill hole.
  751. // Input:   None
  752. // Output:  Type reference to item removed
  753.  
  754. template<class Type> 
  755. Type CoolVector<Type>::shuffle_remove () {
  756.   size_t i = this->curpos;
  757.   if (i == INVALID_POS()) this->remove_error("Type");
  758.   Type value = this->data[i];
  759.   this->data[this->curpos] =            // fill hole at curpos
  760.     this->data[this->number_elements - 1];    // with last element in vector
  761.   this->number_elements--;            // Update element count
  762.   if (this->curpos == this->number_elements)    // If past end of vector
  763.     this->curpos = INVALID_POS();            // Invalidate current position
  764.   return value;                    // Return Vector reference
  765. }
  766.  
  767.  
  768.  
  769. // shuffle_remove -- Destructively remove the first occurrence of an element
  770. //           Shuffle last element up to fill hole
  771. // Input:   Type reference
  772. // Output:  TRUE if element found and removed, FALSE otherwise
  773.  
  774. template<class Type> 
  775. Boolean CoolVector<Type>::shuffle_remove (const Type& value, int dir) {
  776.   size_t start = 0;
  777.   if (dir == -1) start = this->number_elements - 1;
  778.   if (this->find(value, start, dir)) {        // When found
  779.     this->data[this->curpos] =            // fill hole at curpos
  780.       this->data[this->number_elements - 1];    // with last element in vector
  781.     this->number_elements--;            // Update element count
  782.     return TRUE;
  783.   } else 
  784.     return FALSE;
  785. }
  786.  
  787.  
  788. // shuffle_insert_before -- Destructively insert an element before current position
  789. //            Shuffle last element up to fill hole
  790. // Input:           Type reference
  791. // Output:          TRUE if successful, FALSE if could not grow CoolVector
  792.  
  793. template<class Type> 
  794. Boolean CoolVector<Type>::shuffle_insert_before (const Type&  value) {
  795.   if (this->curpos == INVALID_POS())            // If no current position
  796.     return FALSE;                // Return failure flag
  797.   return this->shuffle_insert_before(value, this->curpos);
  798. }
  799.  
  800.  
  801. // shuffle_insert_after -- Destructively insert an element after current position
  802. //            Shuffle last element up to fill hole
  803. // Input:          Type reference
  804. // Output:         TRUE if successful, FALSE if could not grow CoolVector
  805.  
  806. template<class Type> 
  807. Boolean CoolVector<Type>::shuffle_insert_after (const Type&  value) {
  808.   if (this->curpos == INVALID_POS())            // If no current position
  809.     return FALSE;                // Return failure flag
  810.   return this->shuffle_insert_after(value, this->curpos);
  811. }
  812.  
  813. // shuffle_insert_before -- Destructively insert an element before specified index
  814. //            Shuffle element at current position to end of vector
  815. // Input:           Type reference and an index position
  816. // Output:          TRUE if successful, FALSE if could not grow CoolVector
  817.  
  818. template<class Type> 
  819. Boolean CoolVector<Type>::shuffle_insert_before (const Type&  value, size_t index) {
  820.   size_t n = this->number_elements+1;
  821.   if (n >= this->size) {            // If not enough memory
  822.     if (this->alloc_size == INVALID_ALLOCSZ())        // If not allowed to grow
  823.       return FALSE;                // Return failure flag
  824.     this->grow(n);
  825.   }
  826.   this->curpos = index;                // Current position at insertion
  827.   this->data[this->number_elements] =        // Move data at curpos
  828.     this->data[this->curpos];            // to end of vector
  829.   this->data[this->curpos] = value;        // Assign new value
  830.   this->number_elements++;
  831.   return TRUE;                    // Return CoolVector reference
  832. }
  833.  
  834.  
  835.  
  836. // shuffle_insert_after -- Destructively insert an element after specified index
  837. //            Shuffle element at current position to end of vector
  838. // Input:          Type reference and an index position
  839. // Output:         TRUE if successful, FALSE if could not grow CoolVector
  840.  
  841. template<class Type> 
  842. Boolean CoolVector<Type>::shuffle_insert_after (const Type&  value, size_t index) {
  843.   size_t n = this->number_elements+1;
  844.   if (n >= this->size) {            // If not enough memory
  845.     if (this->alloc_size == INVALID_ALLOCSZ())        // If not allowed to grow
  846.       return FALSE;                // Return failure flag
  847.     this->grow(n);
  848.   }
  849.   this->curpos = ++index;            // Current position at insertion
  850.   this->data[this->number_elements] =        // Move data at curpos
  851.     this->data[this->curpos];            // to end of vector
  852.   this->data[this->curpos] = value;        // Assign new value
  853.   this->number_elements++;
  854.   return TRUE;                    // Return CoolVector reference
  855. }
  856.  
  857. #endif // VECTORC
  858.  
  859.